home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / Portable Patmos / src / portable kernel / mac / malloc.c.claimable < prev    next >
Encoding:
Text File  |  1994-11-03  |  12.1 KB  |  880 lines  |  [TEXT/KAHL]
  1. /*
  2.  
  3.  * Copyright (c) 1983 Regents of the University of California.
  4.  
  5.  * All rights reserved.
  6.  
  7.  *
  8.  
  9.  * Redistribution and use in source and binary forms, with or without
  10.  
  11.  * modification, are permitted provided that the following conditions
  12.  
  13.  * are met:
  14.  
  15.  * 1. Redistributions of source code must retain the above copyright
  16.  
  17.  *    notice, this list of conditions and the following disclaimer.
  18.  
  19.  * 2. Redistributions in binary form must reproduce the above copyright
  20.  
  21.  *    notice, this list of conditions and the following disclaimer in the
  22.  
  23.  *    documentation and/or other materials provided with the distribution.
  24.  
  25.  * 3. All advertising materials mentioning features or use of this software
  26.  
  27.  *    must display the following acknowledgement:
  28.  
  29.  *    This product includes software developed by the University of
  30.  
  31.  *    California, Berkeley and its contributors.
  32.  
  33.  * 4. Neither the name of the University nor the names of its contributors
  34.  
  35.  *    may be used to endorse or promote products derived from this software
  36.  
  37.  *    without specific prior written permission.
  38.  
  39.  *
  40.  
  41.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  42.  
  43.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  44.  
  45.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  46.  
  47.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  48.  
  49.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  50.  
  51.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  52.  
  53.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54.  
  55.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  56.  
  57.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  58.  
  59.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  60.  
  61.  * SUCH DAMAGE.
  62.  
  63.  */
  64.  
  65.  
  66.  
  67. #if defined(LIBC_SCCS) && !defined(lint)
  68.  
  69. static char sccsid[] = "@(#)malloc.c    5.11 (Berkeley) 2/23/91";
  70.  
  71. #endif /* LIBC_SCCS and not lint */
  72.  
  73.  
  74.  
  75. /*
  76.  
  77.  * malloc.c (Caltech) 2/21/82
  78.  
  79.  * Chris Kingsley, kingsley@cit-20.
  80.  
  81.  *
  82.  
  83.  * This is a very fast storage allocator.  It allocates blocks of a small 
  84.  
  85.  * number of different sizes, and keeps free lists of each size.  Blocks that
  86.  
  87.  * don't exactly fit are passed up to the next larger size.  In this 
  88.  
  89.  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  90.  
  91.  * This is designed for use in a virtual memory environment.
  92.  
  93.  */
  94.  
  95.  
  96.  
  97. #include <sys/types.h>
  98.  
  99. #include <stdlib.h>
  100.  
  101. #include <string.h>
  102.  
  103. #include <unistd.h>
  104.  
  105. static void morecore(int bucket);
  106. static findbucket(    union overhead *freep,    int srchlen);
  107. void malloc_free_all(void);
  108. void    mysleep(int);
  109.  
  110. #ifndef NULL
  111. #define    NULL 0
  112. #endif
  113.  
  114.  
  115.  
  116.  
  117. /*
  118.  
  119.  * The overhead on a block is at least 4 bytes.  When free, this space
  120.  
  121.  * contains a pointer to the next free block, and the bottom two bits must
  122.  
  123.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  124.  
  125.  * byte is the size index.  The remaining bytes are for alignment.
  126.  
  127.  * If range checking is enabled then a second word holds the size of the
  128.  
  129.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  130.  
  131.  * The order of elements is critical: ov_magic must overlay the low order
  132.  
  133.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  134.  
  135.  */
  136.  
  137. union    overhead {
  138.  
  139.     union    overhead *ov_next;    /* when free */
  140.  
  141.     struct {
  142.  
  143.         u_char    ovu_magic;    /* magic number */
  144.  
  145.         u_char    ovu_index;    /* bucket # */
  146.  
  147. #ifdef RCHECK
  148.  
  149.         u_short    ovu_rmagic;    /* range magic number */
  150.  
  151.         u_int    ovu_size;    /* actual block size */
  152.  
  153. #endif
  154.  
  155.     } ovu;
  156.  
  157. #define    ov_magic    ovu.ovu_magic
  158.  
  159. #define    ov_index    ovu.ovu_index
  160.  
  161. #define    ov_rmagic    ovu.ovu_rmagic
  162.  
  163. #define    ov_size        ovu.ovu_size
  164.  
  165. };
  166.  
  167.  
  168.  
  169. #define    MAGIC        0xef        /* magic # on accounting info */
  170.  
  171. #define RMAGIC        0x5555        /* magic # on range info */
  172.  
  173.  
  174.  
  175. #ifdef RCHECK
  176.  
  177. #define    RSLOP        sizeof (u_short)
  178.  
  179. #else
  180.  
  181. #define    RSLOP        0
  182.  
  183. #endif
  184.  
  185.  
  186.  
  187. /*
  188.  
  189.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  190.  
  191.  * smallest allocatable block is 8 bytes.  The overhead information
  192.  
  193.  * precedes the data area returned to the user.
  194.  
  195.  */
  196.  
  197. #define    NBUCKETS 30
  198.  
  199. static    union overhead *nextf[NBUCKETS];
  200.  
  201.  
  202.  
  203. static    int pagesz;            /* page size */
  204.  
  205. static    int pagebucket;            /* page size bucket */
  206.  
  207.  
  208.  
  209. #ifdef MSTATS
  210.  
  211. /*
  212.  
  213.  * nmalloc[i] is the difference between the number of mallocs and frees
  214.  
  215.  * for a given block size.
  216.  
  217.  */
  218.  
  219. static    u_int nmalloc[NBUCKETS];
  220.  
  221. #include <stdio.h>
  222.  
  223. #endif
  224.  
  225.  
  226.  
  227. #if defined(DEBUG) || defined(RCHECK)
  228.  
  229. #define    ASSERT(p)   if (!(p)) botch("p")
  230.  
  231. #include <stdio.h>
  232.  
  233. static
  234.  
  235. botch(s)
  236.  
  237.     char *s;
  238.  
  239. {
  240.  
  241.     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  242.  
  243.      (void) fflush(stderr);        /* just in case user buffered it */
  244.  
  245.     abort();
  246.  
  247. }
  248.  
  249. #else
  250. #ifndef ASSERT
  251. #define    ASSERT(p)
  252. #endif
  253. #endif
  254.  
  255.  
  256.  
  257. void *
  258.  
  259. malloc(nbytes)
  260.  
  261.     size_t nbytes;
  262.  
  263. {
  264.  
  265.       register union overhead *op;
  266.  
  267.       register int bucket, n;
  268.  
  269.     register unsigned amt;
  270.  
  271.  
  272.  
  273.     /*
  274.  
  275.      * First time malloc is called, setup page size and
  276.  
  277.      * align break pointer so all data will be page aligned.
  278.  
  279.      */
  280.  
  281.     if (pagesz == 0) 
  282.  
  283.         {
  284.  
  285.         pagesz = n = getpagesize();
  286.  
  287.         bucket = 0;
  288.  
  289.         amt = 8;
  290.  
  291.         while (pagesz > amt) 
  292.  
  293.             {
  294.  
  295.             amt <<= 1;
  296.  
  297.             bucket++;
  298.  
  299.             }
  300.  
  301.         pagebucket = bucket;
  302.  
  303.         }
  304.  
  305.     /*
  306.  
  307.      * Convert amount of memory requested into closest block size
  308.  
  309.      * stored in hash buckets which satisfies request.
  310.  
  311.      * Account for space used per block for accounting.
  312.  
  313.      */
  314.  
  315.     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
  316.  
  317. #ifndef RCHECK
  318.  
  319.         amt = 8;    /* size of first bucket */
  320.  
  321.         bucket = 0;
  322.  
  323. #else
  324.  
  325.         amt = 16;    /* size of first bucket */
  326.  
  327.         bucket = 1;
  328.  
  329. #endif
  330.  
  331.         n = -(sizeof (*op) + RSLOP);
  332.  
  333.     } else {
  334.  
  335.         amt = pagesz;
  336.  
  337.         bucket = pagebucket;
  338.  
  339.     }
  340.  
  341.     while (nbytes > amt + n) {
  342.  
  343.         amt <<= 1;
  344.  
  345.         if (amt == 0)
  346.  
  347.             return (NULL);
  348.  
  349.         bucket++;
  350.  
  351.     }
  352.  
  353.     /*
  354.  
  355.      * If nothing in hash bucket right now,
  356.  
  357.      * request more memory from the system.
  358.  
  359.      */
  360.  
  361.       if ((op = nextf[bucket]) == NULL) {
  362.  
  363.           morecore(bucket);
  364.  
  365.           if ((op = nextf[bucket]) == NULL)
  366.  
  367.               return (NULL);
  368.  
  369.     }
  370.  
  371.     /* remove from linked list */
  372.  
  373.       nextf[bucket] = op->ov_next;
  374.  
  375.     op->ov_magic = MAGIC;
  376.  
  377.     op->ov_index = bucket;
  378.  
  379. #ifdef MSTATS
  380.  
  381.       nmalloc[bucket]++;
  382.  
  383. #endif
  384.  
  385. #ifdef RCHECK
  386.  
  387.     /*
  388.  
  389.      * Record allocated size of block and
  390.  
  391.      * bound space with magic numbers.
  392.  
  393.      */
  394.  
  395.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  396.  
  397.     op->ov_rmagic = RMAGIC;
  398.  
  399.       *(u_short *)((char *)(op + 1) + op->ov_size) = RMAGIC;
  400.  
  401. #endif
  402.  
  403.       return ((char *)(op + 1));
  404.  
  405. }
  406.  
  407.  
  408.  
  409. static void *emptyblock(size_t sz);
  410.  
  411. /*
  412.  
  413.  * Allocate more memory to the indicated bucket.
  414.  
  415.  */
  416.  
  417. static void morecore(int bucket)
  418. {
  419.  
  420.       register union overhead *op;
  421.  
  422.     register int sz;        /* size of desired block */
  423.  
  424.       int amt;            /* amount to allocate */
  425.  
  426.       int nblks;            /* how many blocks we get */
  427.  
  428.  
  429.  
  430.     /*
  431.  
  432.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  433.  
  434.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  435.  
  436.      */
  437.  
  438.     sz = 1 << (bucket + 3);
  439.  
  440. #ifdef DEBUG
  441.  
  442.     ASSERT(sz > 0);
  443.  
  444. #else
  445.  
  446.     if (sz <= 0)
  447.  
  448.         return;
  449.  
  450. #endif
  451.  
  452.     if (sz < pagesz) {
  453.  
  454.         amt = pagesz;
  455.  
  456.           nblks = amt / sz;
  457.  
  458.     } else {
  459.  
  460.         amt = sz + pagesz;
  461.  
  462.         nblks = 1;
  463.  
  464.     }
  465.  
  466.     op = (union overhead *)emptyblock(amt);
  467.  
  468.     /* no more room! */
  469.  
  470.       if (!op)
  471.  
  472.           return;
  473.  
  474.     /*
  475.  
  476.      * Add new memory allocated to that on
  477.  
  478.      * free list for this hash bucket.
  479.  
  480.      */
  481.  
  482.       nextf[bucket] = op;
  483.  
  484.       while (--nblks > 0) {
  485.  
  486.         op->ov_next = (union overhead *)((char *)op + sz);
  487.  
  488.         op = (union overhead *)((char *)op + sz);
  489.  
  490.       }
  491.  
  492. }
  493.  
  494.  
  495.  
  496. void
  497.  
  498. free(cp)
  499.  
  500.     void *cp;
  501.  
  502. {   
  503.  
  504.       register int size;
  505.  
  506.     register union overhead *op;
  507.  
  508.  
  509.  
  510.       if (cp == NULL)
  511.  
  512.           return;
  513.  
  514.     op = (union overhead *)((char *)cp - sizeof (union overhead));
  515.  
  516. #ifdef DEBUG
  517.  
  518.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  519.  
  520. #else
  521.  
  522.     if (op->ov_magic != MAGIC)
  523.  
  524.         return;                /* sanity */
  525.  
  526. #endif
  527.  
  528. #ifdef RCHECK
  529.  
  530.       ASSERT(op->ov_rmagic == RMAGIC);
  531.  
  532.     ASSERT(*(u_short *)((char *)(op + 1) + op->ov_size) == RMAGIC);
  533.  
  534. #endif
  535.  
  536.       size = op->ov_index;
  537.  
  538.       ASSERT(size < NBUCKETS);
  539.  
  540.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  541.  
  542.       nextf[size] = op;
  543.  
  544. #ifdef MSTATS
  545.  
  546.       nmalloc[size]--;
  547.  
  548. #endif
  549.  
  550. }
  551.  
  552.  
  553.  
  554. /*
  555.  
  556.  * When a program attempts "storage compaction" as mentioned in the
  557.  
  558.  * old malloc man page, it realloc's an already freed block.  Usually
  559.  
  560.  * this is the last block it freed; occasionally it might be farther
  561.  
  562.  * back.  We have to search all the free lists for the block in order
  563.  
  564.  * to determine its bucket: 1st we make one pass thru the lists
  565.  
  566.  * checking only the first block in each; if that fails we search
  567.  
  568.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  569.  
  570.  * is extern so the caller can modify it).  If that fails we just copy
  571.  
  572.  * however many bytes was given to realloc() and hope it's not huge.
  573.  
  574.  */
  575.  
  576. int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  577.  
  578.  
  579.  
  580. void *
  581.  
  582. realloc(cp, nbytes)
  583.  
  584.     void *cp; 
  585.  
  586.     size_t nbytes;
  587.  
  588. {   
  589.  
  590.       register u_int onb;
  591.  
  592.     register int i;
  593.  
  594.     union overhead *op;
  595.  
  596.       char *res;
  597.  
  598.     int was_alloced = 0;
  599.  
  600.  
  601.  
  602.       if (cp == NULL)
  603.  
  604.           return (malloc(nbytes));
  605.  
  606.     op = (union overhead *)((char *)cp - sizeof (union overhead));
  607.  
  608.     if (op->ov_magic == MAGIC) {
  609.  
  610.         was_alloced++;
  611.  
  612.         i = op->ov_index;
  613.  
  614.     } else {
  615.  
  616.         /*
  617.  
  618.          * Already free, doing "compaction".
  619.  
  620.          *
  621.  
  622.          * Search for the old block of memory on the
  623.  
  624.          * free list.  First, check the most common
  625.  
  626.          * case (last element free'd), then (this failing)
  627.  
  628.          * the last ``realloc_srchlen'' items free'd.
  629.  
  630.          * If all lookups fail, then assume the size of
  631.  
  632.          * the memory block being realloc'd is the
  633.  
  634.          * largest possible (so that all "nbytes" of new
  635.  
  636.          * memory are copied into).  Note that this could cause
  637.  
  638.          * a memory fault if the old area was tiny, and the moon
  639.  
  640.          * is gibbous.  However, that is very unlikely.
  641.  
  642.          */
  643.  
  644.         if ((i = findbucket(op, 1)) < 0 &&
  645.  
  646.             (i = findbucket(op, realloc_srchlen)) < 0)
  647.  
  648.             i = NBUCKETS;
  649.  
  650.     }
  651.  
  652.     onb = 1 << (i + 3);
  653.  
  654.     if (onb < pagesz)
  655.  
  656.         onb -= sizeof (*op) + RSLOP;
  657.  
  658.     else
  659.  
  660.         onb += pagesz - sizeof (*op) - RSLOP;
  661.  
  662.     /* avoid the copy if same size block */
  663.  
  664.     if (was_alloced) {
  665.  
  666.         if (i) {
  667.  
  668.             i = 1 << (i + 2);
  669.  
  670.             if (i < pagesz)
  671.  
  672.                 i -= sizeof (*op) + RSLOP;
  673.  
  674.             else
  675.  
  676.                 i += pagesz - sizeof (*op) - RSLOP;
  677.  
  678.         }
  679.  
  680.         if (nbytes <= onb && nbytes > i) {
  681.  
  682. #ifdef RCHECK
  683.  
  684.             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  685.  
  686.             *(u_short *)((char *)(op + 1) + op->ov_size) = RMAGIC;
  687.  
  688. #endif
  689.  
  690.             return(cp);
  691.  
  692.         } else
  693.  
  694.             free(cp);
  695.  
  696.     }
  697.  
  698.       if ((res = malloc(nbytes)) == NULL)
  699.  
  700.           return (NULL);
  701.  
  702.       if (cp != res)        /* common optimization if "compacting" */
  703.  
  704.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  705.  
  706.       return (res);
  707.  
  708. }
  709.  
  710.  
  711.  
  712. /*
  713.  
  714.  * Search ``srchlen'' elements of each free list for a block whose
  715.  
  716.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  717.  
  718.  * Return bucket number, or -1 if not found.
  719.  
  720.  */
  721.  
  722. static
  723.  
  724. findbucket(
  725.  
  726.     union overhead *freep,
  727.  
  728.     int srchlen)
  729.  
  730. {
  731.  
  732.     register union overhead *p;
  733.  
  734.     register int i, j;
  735.  
  736.  
  737.  
  738.     for (i = 0; i < NBUCKETS; i++) {
  739.  
  740.         j = 0;
  741.  
  742.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  743.  
  744.             if (p == freep)
  745.  
  746.                 return (i);
  747.  
  748.             j++;
  749.  
  750.         }
  751.  
  752.     }
  753.  
  754.     return (-1);
  755.  
  756. }
  757.  
  758.  
  759.  
  760. #ifdef MSTATS
  761.  
  762. /*
  763.  
  764.  * mstats - print out statistics about malloc
  765.  
  766.  * 
  767.  
  768.  * Prints two lines of numbers, one showing the length of the free list
  769.  
  770.  * for each size category, the second showing the number of mallocs -
  771.  
  772.  * frees for each size category.
  773.  
  774.  */
  775.  
  776. mstats(s)
  777.  
  778.     char *s;
  779.  
  780. {
  781.  
  782.       register int i, j;
  783.  
  784.       register union overhead *p;
  785.  
  786.       int totfree = 0,
  787.  
  788.       totused = 0;
  789.  
  790.  
  791.  
  792.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  793.  
  794.       for (i = 0; i < NBUCKETS; i++) {
  795.  
  796.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  797.  
  798.               ;
  799.  
  800.           fprintf(stderr, " %d", j);
  801.  
  802.           totfree += j * (1 << (i + 3));
  803.  
  804.       }
  805.  
  806.       fprintf(stderr, "\nused:\t");
  807.  
  808.       for (i = 0; i < NBUCKETS; i++) {
  809.  
  810.           fprintf(stderr, " %d", nmalloc[i]);
  811.  
  812.           totused += nmalloc[i] * (1 << (i + 3));
  813.  
  814.       }
  815.  
  816.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  817.  
  818.         totused, totfree);
  819.  
  820. }
  821.  
  822. #endif
  823.  
  824.  
  825.  
  826. #include <Memory.h>
  827.  
  828.  
  829.  
  830. static long old_chain = 0;
  831.  
  832.  
  833.  
  834. void malloc_free_all(void)
  835.  
  836.     {
  837.  
  838.     long *ptr = (void *)old_chain;
  839.  
  840.     while (ptr)
  841.  
  842.         {
  843.  
  844.         long *nxt = (void *)*ptr;
  845.  
  846.         DisposPtr((Ptr)ptr);
  847.  
  848.         ptr = nxt;
  849.  
  850.         }
  851.  
  852.     bzero(nextf, sizeof nextf);
  853.  
  854.     old_chain = 0;
  855.  
  856.     }
  857.  
  858.  
  859.  
  860. static void *emptyblock(size_t sz)
  861.  
  862.     {
  863.  
  864.     long *chain = (void *)NewPtrClear(sz+8);
  865.  
  866.     if (!chain) return 0;
  867.  
  868.     *chain = old_chain;
  869.  
  870.     old_chain = (long)chain++;
  871.  
  872.     *chain++ = sz;
  873.  
  874.     mysleep(1);
  875.  
  876.     return chain;
  877.  
  878.     }
  879.  
  880.